class Solution:
	# @param s, a string
	# @param wordDict, a set<string>
	# @return a boolean
	def wordBreak(self, s, wordDict):
		if len(s) < 1:
			return False
		check = [False for i in xrange(len(s))]
		for i in xrange(len(s)):
			for j in xrange(i-1,-1,-1):
				if check[j]:
					if s[j+1:i+1] in wordDict:
						check[i] = True
						break
			if check[i] is not True:
				if s[:i+1] in wordDict:
					check[i] = True
		return check[-1]

if __name__ == '__main__':
	so = Solution()
	s = 'talescoped'
	d = set()
	d.add('tale')
	d.add('scoped')
	d.add('talescope')
	print so.wordBreak(s,d)